#include <bits/stdc++.h>
using namespace std;

/*
3217. 从链表中移除在数组中存在的节点
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和一个链表的头节点 head。从链表中移除所有存在于 nums 中的节点后，返回修改后的链表的头节点。

 

示例 1：

输入： nums = [1,2,3], head = [1,2,3,4,5]

输出： [4,5]

解释：



移除数值为 1, 2 和 3 的节点。

示例 2：

输入： nums = [1], head = [1,2,1,2,1,2]

输出： [2,2,2]

解释：



移除数值为 1 的节点。

示例 3：

输入： nums = [5], head = [1,2,3,4]

输出： [1,2,3,4]

解释：



链表中不存在值为 5 的节点。

 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 105
nums 中的所有元素都是唯一的。
链表中的节点数在 [1, 105] 的范围内。
1 <= Node.val <= 105
输入保证链表中至少有一个值没有在 nums 中出现过。
*/


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 法一
class Solution {
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        // hash O(1)
        unordered_set<int> delSet(nums.begin(), nums.end());
        // vir Head  简化移除
        ListNode dummy(0, head);
        ListNode* pre = &dummy;     // pre pointer

        while (pre->next) {
            if (delSet.count(pre->next->val))   pre->next = pre->next->next;
            else    pre = pre->next;
        }
        return dummy.next;
    }
};

// 法二
class Solution {
    static constexpr int MAXV = 100000; // 题设val范围1~1e5，定长数组足够覆盖
public:
    ListNode* modifiedList(vector<int>& nums, ListNode* head) {
        // 位图标记：用1标记需移除的val，O(1)查找（无哈希冲突，比unordered_set更快）
        std::array<uint8_t, MAXV + 1> mark{}; // 栈上分配，默认全0，仅占~100KB
        for (int x : nums) mark[x] = 1; // 标记需移除的数值

        ListNode dummy(0, head); // 虚拟头节点，简化头节点删除逻辑
        ListNode* pre = &dummy;  // 前驱节点，用于跳过待删除节点

        while (pre->next) { // 遍历链表（当前处理节点为pre->next）
            int v = pre->next->val;
            if (mark[v])  pre->next = pre->next->next;      // 若当前节点需移除，直接跳过   
            else  pre = pre->next;                          // 无需移除，前驱节点后移    
        }
        return dummy.next;
    }
};